#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<stack>
#include<map>
#include<list>
#include<locale>
#include "lex.yy.h"

using namespace std;
//global variables
stack<string> stck;
map<char, int> mp;
vector<vector<string> > parse_table;
vector<string> states;
map<char, string> sym_names;

class Node {
private:
	vector<Node*> children;
	int id;
	char value;
public:
	Node(char val) {
		this->value = val;
	}
	~Node() {
		cout << "Destructor called" << endl;
	}
	vector<Node*> get_children();
	void set_children(vector<Node*> );
	int get_id();
	void set_id(int);
	char get_value();
	void set_value(char);
	void add_child(Node*);
	void remove_child(Node*);
};
vector<Node*> Node::get_children() {
	return this->children;
}
void Node::set_children(vector<Node*> subtree) {
	this->children = subtree;
}
int Node::get_id() {
	return this->id;
}
void Node::set_id(int id_val) {
	this->id = id_val;
}
char Node::get_value() {
	return this->value;
}
void Node::set_value(char val) {
	this->value = val;
}
void Node::add_child(Node* c) {
	this->children.push_back(c);
}

void Node::remove_child(Node* c) {
	for (vector<Node*>::iterator it = this->children.begin(); it
			< this->children.end(); it++) {
		if ((*it) == c) {
			this->children.erase(it);
		}
	}
}
//prints a tree given a "Node" element
void print_parse_tree(Node* root, string tab) {
	if (sym_names.find(root->get_value()) != sym_names.end()) {
		cout << sym_names.find(root->get_value())->second << endl;
	} else {
		cout << root->get_value() << endl;
	}
	tab += "  ";
	for (unsigned int i = 0; i < root->get_children().size(); i++) {
		cout << tab;
		print_parse_tree(root->get_children()[i], tab);
	}

}

Node* root = new Node('P');
int root_has_child(char b) {
	if (root == NULL) {
		return 0;
	}
	int a;
	for (a = 0; a < root->get_children().size(); a++) {
		if (root->get_children()[a]->get_value() == b) {
			return 1;
		}
	}
	return 0;
}

Node* find_child(char b) {
	int a;
	for (a = 0; a < root->get_children().size(); a++) {
		if (root->get_children()[a]->get_value() == b) {
			return root->get_children()[a];
		}
	}
	return NULL;
}
void restructure_tree(list<char> children, char parent) {
	int i;
	Node* par = new Node(parent);
	for (list<char>::iterator it = children.begin(); it != children.end(); it++) {
		//cout << *it << endl;
		if (root_has_child(*it)) {
			Node* n = find_child(*it);
			par->add_child(n);
			root->remove_child(n);

		} else {
			Node* c = new Node(*it);
			par->add_child(c);
		}
	}
	root->add_child(par);
}
char reduce(string prodn) {
	list<char> children;
	char parent;
	if (prodn.size() < 3) {
		return prodn.data()[0];
	}
	string right = prodn.substr(2, prodn.size() - 1);
	//cout << "redn string " << right << endl;
	string handle = "";
	//cout << "on top before pop " << stck.top() << endl;
	while (handle != right) {
		if (!stck.empty()) {
			stck.pop();
			children.push_front(stck.top().data()[0]);
			handle = stck.top() + handle;
			stck.pop();
		}
	}
	//cout << "on top after pop " << stck.top() << endl;
	parent = prodn.data()[0];
	restructure_tree(children, parent);
	return prodn.data()[0];
}

int initialize() {
	ifstream parser_file("input.parse");
	string line;

	int line_no = 1;
	int i = 0;
	if (parser_file.is_open()) {
		while (parser_file.good()) {
			getline(parser_file, line);
			//cout << "DEBUG :: " << line << endl;

			char p[line.size() + 1];//have to create a char array since strtok works only with char arrays.
			p[line.size()] = 0; //last character is a null.
			memcpy(p, line.c_str(), line.size());

			int j = 0;
			vector<string> row;
			char *tokens;
			tokens = strtok(p, " ");
			while (tokens != NULL) {
				if (i == 0) { //store the first row as chars in language
					if (j == 0) {
						tokens = strtok(NULL, " ");
						j++;
						continue;
					}
					mp.insert(pair<char, int> (*tokens, j - 1));
				} else if (j == 0) { //store first column as states
					states.push_back(tokens);
				} else { //the rest forms the transition table
					row.push_back(tokens);
				}

				tokens = strtok(NULL, " ");
				j++;
			}
			if (row.size() != 0) {
				//cout << i << " : " << row.size() << endl;
				parse_table.push_back(row);
			}
			i++;
		}
		//cout << states.size() << endl;
		//cout << parse_table.size() << endl;
		//cout << chars_in_language.size() <<endl;
		parser_file.close();

	} else {
		cout << "ERROR :: UNABLE TO OPEN PARSE FILE" << endl;
		exit(1);
	}

	sym_names.insert(pair<char, string> ('l', "loop"));
	sym_names.insert(pair<char, string> ('i', "identifier"));
	sym_names.insert(pair<char, string> ('p', "print"));
	sym_names.insert(pair<char, string> ('n', "number"));
	sym_names.insert(pair<char, string> ('A', "statement"));
	sym_names.insert(pair<char, string> ('S', "statements"));
	sym_names.insert(pair<char, string> ('P', "program"));
	sym_names.insert(pair<char, string> ('D', "function-name"));
	sym_names.insert(pair<char, string> ('E', "parameters"));
	sym_names.insert(pair<char, string> ('B', "parameter"));
	sym_names.insert(pair<char, string> ('C', "function-call"));

	return 0;
}

int main(int args, char* argv[]) {
	initialize();
	string sentence = get_sentence(argv[2]);
	sentence += "$";
	stck.push("0");
	//cout << sentence << endl;
	int i, x = 0, y;
	for (i = 0; i < sentence.size(); i++) {

		y = mp[sentence.data()[i]];
		//cout << "current state" << x << endl;
		//cout << "current input" << sentence.data()[i] << endl;
		if (parse_table[x][y] == "a") {
			cout << "THIS IS VALID SYNTAX" << endl;
			//cout << root->get_value() << endl;
			//cout << root->get_children()[1]->get_value() <<endl;
			cout << "PARSE TREE" << endl;
			print_parse_tree(root->get_children()[0], "");
		} else if (parse_table[x][y] == "-") {
			cout << "SYNTAX ERROR" << endl;
			exit(0);
		} else if (isdigit(parse_table[x][y][0])) {
			stck.push(sentence.substr(i, 1));
			stck.push(parse_table[x][y].data());
			x = atoi(parse_table[x][y].data());
		} else {
			sentence[--i] = reduce(parse_table[x][y].data());
			i--;
			x = atoi(stck.top().data());
			//cout << "new x: " << x << endl;
		}
	}
	return 0;
}
